package cn.corffen.test.algorithm.leetcode.easy.dp;

import com.corffen.libsource.StdRandom;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class DynamicProgrammingDemo {

    public static final int seed = 10000;

    public static final int TYPE_RECURSION = 1;
    public static final int TYPE_MAP = 2;
    public static final int TYPE_DYNAMIC = 3;

    public static void main(String[] args) {
//        printMethodConsume(TYPE_RECURSION);
//        printMethodConsume(TYPE_MAP);
//        printMethodConsume(TYPE_DYNAMIC);
//        int n = seed;
//        int dynamic = getClimbingWays2(n);
//        System.out.println("dynamic:" + dynamic);
//        int recursion = getClimbingWays(n);
//        System.out.println("recursion:" + recursion);
//        int map = getClimbingWaysWithMemory(n, new HashMap<>());
//        System.out.println("map:" + map);

        printLengthOfLIS();
    }

    private static void printLengthOfLIS() {
        int[] numbers = generateArray(10);
        System.out.println(Arrays.toString(numbers));
        System.out.println("最大子长度为:" + lengthOfLIS(numbers));
    }

    public static int[] generateArray(int n) {
        int[] numbers = new int[n];
        for (int i = 01; i < n; i++) {
            numbers[i] = i + 1;
        }
        StdRandom.shuffle(numbers);
        return numbers;
    }

    private static void printMethodConsume(int type) {
        for (int i = 0; i < 5; i++) {
            long start = System.currentTimeMillis();
            int n = (int) (seed * Math.pow(2, i));
            String method = "";
            if (type == TYPE_RECURSION) {
                getClimbingWays(n);
                method = "递归";
            } else if (type == TYPE_MAP) {
                getClimbingWaysWithMemory(n, new HashMap<Integer, Integer>());
                method = "备忘录算法";
            } else if (type == TYPE_DYNAMIC) {
                int climbingWays2 = getClimbingWays2(n);
                method = "动态规划";
            }
            long end = System.currentTimeMillis();
            System.out.println(method + n + "个数据,total time:" + (end - start));
        }
    }


    public static int getClimbingWays(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        return getClimbingWays(n - 1) + getClimbingWays(n - 2);
    }

    public static int getClimbingWaysWithMemory(int n, HashMap<Integer, Integer> map) {
        if (n < 1) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        if (map.containsKey(n)) {
            return map.get(n);
        } else {
            int value = getClimbingWaysWithMemory(n - 1, map) + getClimbingWaysWithMemory(n - 2, map);
            map.put(n, value);
            return value;
        }
    }

    /**
     * base case 有两个,dp[1] = 1 dp[2]
     * 状态转移方程: dp[n] = dp[n-1]+dp[n-2]
     * 在迭代过程中,每个值 都需要前面两个值之和.
     *
     * @param n
     * @return
     */
    public static int getClimbingWays2(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int a = 1;
        int b = 2;
        int temp = 0;
        for (int i = 3; i <= n; i++) {
            temp = a + b;
            a = b;
            b = temp;
        }
        return temp;
    }


    public int fib(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    /**
     * 斐波那契 从第三项开始,每一项都是前两项之和
     * 所以在迭代过程中,只需要保留记录前两次的数据,即可.
     * 前两项在一开始就知道值了.
     * 然后在推进过程中,不断地更新这两个值.
     *
     * @param n
     * @return
     */
    public int fib2(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        int first = 1;
        int second = 1;
        for (int i = 3; i <= n; i++) {
            int temp = first + second;
            first = second;
            second = temp;
        }
        return second;
    }

    public List<Integer> triangle(int n) {
        List<Integer> triangle = new ArrayList<>();
        if (n <= 0) {
            return triangle;
        }
        for (int i = 0; i < n; i++) {
            triangle.add(1);//最后一项是1
            for (int j = i - 1; j > 0; j--) {
                //更新上一次的结果.
                triangle.set(j, triangle.get(j - 1) + triangle.get(j));
            }
        }
        return triangle;
    }

    /**
     * 最长递归子长度
     * <p>
     * 思路:
     * 1.要明确dp数组的含义.这里表示第i个数,最长的递归子长度
     * 2.用数学归纳法表示,如果已知前i-1个数的函数dp,那么求出第
     * i个数的函数值.
     * <p>
     * 如果第i个数遍历与它前面的数进行比较,如果大于,那么其长度就为该dp[j]的值加1
     * 当然还要与之前的最大值进行比较  取其较大值
     * <p>
     * 动态规划,就是在遍历的过程中,当前的值可以用之前的状态推导出来.
     * 有几个点需要明白;
     * 1.base case是什么. 当只有一个元素时,长度为1.
     * 2.dp函数表示的是什么.
     * 3.状态转移方程,如何表示.
     * <p>
     * <p>
     * 时间复杂度为O(n方);
     *
     * @param numbers
     * @return
     */
    public static int lengthOfLIS(int[] numbers) {
        int len = numbers.length;
        int[] dp = new int[len + 1];
        Arrays.fill(dp, 1);

        for (int i = 0; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (numbers[i] > numbers[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int max = 0;
        for (int i = 0; i < dp.length; i++) {
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    /**
     * 最大子数组.
     * base case dp[0] = numbers[0]
     * 明确dp函数的意义:  以第i个数为结尾的最大子数组的和.
     * 状态转移方程: dp[i] = max(numbers[i],dp[i-1]+numbers[i]);
     * <p>
     * 迭代增长的过程中:
     * 当前的 dp[i]为上一次的值+当前number,与当前的number进行比较.的较大值.
     *
     * @param numbers
     * @return
     */
    public static int maxSubArray(int[] numbers) {
        int length = numbers.length;
        if (length == 0) {
            return 0;
        }
        int[] dp = new int[length];
        dp[0] = numbers[0];
        for (int i = 1; i < length; i++) {
            dp[i] = Math.max(numbers[i], dp[i - 1] + numbers[i]);
        }
        int result = Integer.MIN_VALUE;
        for (int i = 0; i < length; i++) {
            result = Math.max(result, dp[i]);
        }
        return result;
    }

    /**
     * 状态压缩
     *
     * @param numbers
     * @return
     */
    public static int maxSubArray2(int[] numbers) {
        int length = numbers.length;
        if (length == 0) {
            return 0;
        }
        int current = numbers[0];
        int last = numbers[0]; //只需要保存上一次的结果就行
        int max = numbers[0];
        for (int i = 1; i < length; i++) {
            current = Math.max(numbers[i], last + numbers[i]);
            last = current;

            max = Math.max(max, current);
        }
        return max;
    }

    /**
     * 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
     * <p>
     * 如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
     * <p>
     * 注意：你不能在买入股票前卖出股票。
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int maxProfit = 0;
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                if (prices[j] > prices[i]) {
                    maxProfit = Math.max(maxProfit, prices[j] - prices[i]);
                }
            }
        }
        return maxProfit;
    }

    /**
     * 假设每一天都是在历史最低的那一天卖出,那么当天的最大收益就是
     * prices[i] - minPrice
     * 遍历完之后,在所有的最大收益中取出最大值.
     *
     * @param prices
     * @return
     */
    public int maxProfit1(int[] prices) {
        int len = prices.length;
        int maxProfit = 0;
        int minPrice = Integer.MAX_VALUE;
        for (int i = 0; i < len; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else if (prices[i] - minPrice > maxProfit) {
                maxProfit = prices[i] - minPrice;
            }
        }
        return maxProfit;
    }


    /**
     * 打家劫舍
     * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
     * <p>
     * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * 输入：[1,2,3,1]
     * 输出：4
     * 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     * 偷窃到的最高金额 = 1 + 3 = 4 。
     * 示例 2：
     * <p>
     * 输入：[2,7,9,3,1]
     * 输出：12
     * 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     * 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
     *
     * @param nums
     * @return f(n) = f(n-2)+a[n],f(n-1);
     */
    public int rob(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        if (len == 1) {
            return nums[0];
        }
        int[] dp = new int[len];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[1], nums[0]);
        for (int i = 2; i < len; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        int max = 0;
        for (int i = 0; i < len; i++) {
            max = Math.max(dp[i], max);
        }
        return max;
    }

    public int rob2(int[] nums){
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        if (len == 1) {
            return nums[0];
        }
        int first = nums[0];
        int second = Math.max(nums[0],nums[1]);
        int max = second;
        for (int i = 2; i < len; i++) {
            max = Math.max(first + nums[i], second);
            first = second;
            second = max;
        }
        return max;

    }
}
